[前端算法]关于整理思路的一点启发

date

Sep 3, 2022

slug

[前端算法]关于整理思路的一点启发

status

Published

引言

最近在换工作，虽然已经是一个大叔级程序员了，但是三件套还是少不了：更新简历、刷 Boss、刷面试题。今年行情有点寒气逼人，前端人也要开始卷算法了，目前看，难度主要以简单为主，少数中等（大厂多一些）。

我的情况是，三年之前刷过三十来道 leetcode，现在看来数量不够，这次必须再捡起来刷一刷。其中有一道二叉树 medium 题目，题目不算难，但是我觉得对我启发挺大，特别是几轮分析过程，本文就分享一下我整理思路的过程，希望对大家也有所启发。

第一轮

第一轮主要是看题目：

给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

第一件事就是题目的阅读理解。我刷题不多，时间一长，二叉搜索树这个概念都有些模糊了，就先从查概念解释开始：二叉搜索树就是左子树比根小，右子树比根大的二叉树。再结合示例，就很容易能明白题目意思：给定数字序列 1-n 能排出多少种二叉搜索树。

然后就是分析如何解题了，也就是找到计算排列数量的办法，我很快联想到数学中的排列组合了，排列组合是可以转化成公式的，比如 10 个小学生排队，有多少排法，就可以转化成公式 10 的阶乘。

但是二叉搜索树的排列又不太一样，根节点有 n 种，但再往下有几种排列，怎么计算？有点没头绪了，思考了几分钟，找不到规律。有点想翻答案了…

第二轮

第二轮就是关键的思路整理，第一轮遇到困难，差点就去翻答案了，然后被自己摁住了，沉下心来再次整理思路。

思考的方向就是如何从题目细节，找到排列的规律，第一个想到的就是二叉搜索树，好好来捋一下它的概念：左边比根小，右边比根大，这不就和有序数组类似么，选定一个数组元素作为根之后，左边的数字就是左子树，右边的就是右子树，其实用数组表示二叉树，在数据结构中有，时间太久忘记了。

举个例子（有时候用实例去想，更容易理解），给定 n=5 ，用 2 作为树根，那就左子树就是 1，右子树就是 3-5，1 的排列就 1 种。那右子树的 3-5 呢，怎么排列？好像又卡住了。

关键突破口来了，既然是有序数组，3-5 的排列是否和 1-3 一样？统一减去 2，并不影响排序的顺序，所以排序的数量就是一样的！

那么，不管数字是多少，我们都可以抽象成是 1-n 的排列！我们就可以用迭代去解决问题。

抽象之后就是：给定 1-n 的数字序列，当选定一个数字 k(1≤k≤n) 作为根时，f(k) = f(k-1) * f(n-k) . f(1), f(2) 可以直接给出。

第一版代码来了，找到规律之后倒是没写几行代码，提交之后马上就通过了。

var numTrees = function(n) {
	  // 注意：n=0 时，需要处理为 1，因为 n=0 表示没有子节点，也是一种排列。
    if (n < 3) return n || 1

    let nums = 0
    for (let i=1; i<=n; i++) {
        nums += numTrees(i-1) * numTrees(n-i)
    }

    return nums
};

第三轮

第三轮是优化，第二轮的思路整理让我最终找出了解题思路，也给了我很大的信心和启发，但是复杂度比较高，有很大优化空间。

优化思路也是从 3-5 的排列和 1-3 一样去入手，很容易会发现：数组过半之后，数组后半段的排列数量其实和前半段一样的！也就是后半段没必要计算了，直接在前半段基础上翻倍就好了，唯一需要考虑的就是数组长度要分奇偶数来处理。

代码也很简单，直接贴一下，供参考。

var numTrees = function(n) {
    if (n < 3) return n || 1

    let nums = 0
    let mid = Math.ceil(n / 2)

    let i
    for (i=1; i<mid; i++) {
        nums += numTrees(i-1) * numTrees(n-i)
    }
		// 数据长度分奇偶处理
    if (n&1) {
        nums = nums * 2 + numTrees(i-1) * numTrees(n-i)
    } else {
        nums = (nums + numTrees(i-1) * numTrees(n-i)) * 2
    }

    return nums
};

总结

遇到困难，保持耐心，从细节入手，寻找一般规律。